# 389.找不同
# https://leetcode.cn/problems/find-the-difference/?envType=study-plan-v2&envId=programming-skills

# 给定两个字符串s和t，它们只包含小写字母。
# 字符串t由字符串s随机重排，然后在随机位置添加一个字母。
# 请找出在t中被添加的字母。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        """
        方法2: ASCII码求和法
        时间复杂度: O(n)
        空间复杂度: O(1)
        """
        # 计算两个字符串的ASCII码总和
        sum_s = sum(ord(char) for char in s)
        sum_t = sum(ord(char) for char in t)
        
        # 差值对应的字符就是被添加的字符
        return chr(sum_t - sum_s)
    
    def findTheDifference3(self, s: str, t: str) -> str:
        """
        方法3: 异或法（最优解）
        时间复杂度: O(n)
        空间复杂度: O(1)
        原理：相同的字符异或结果为0，最后剩下的就是被添加的字符
        """
        result = 0
        
        # 对s中所有字符进行异或
        for char in s:
            result ^= ord(char)
        
        print(result)

        result2 = 0
        # 对t中所有字符进行异或
        for char in t:
            result2 ^= ord(char)
            result ^= ord(char)
        
        print(result2)
        print(result)

        # 最后的结果就是被添加字符的ASCII码
        return chr(result)

    
# 测试代码
if __name__ == "__main__":
    solution = Solution()
    
    # 测试用例1
    s1, t1 = "a", "ba"
    result1 = solution.findTheDifference3(s1, t1)
    print(f"测试1: s='{s1}', t='{t1}' -> 被添加的字符: '{result1}'")
    
    # # 测试用例2
    # s2, t2 = "", "y"
    # result2 = solution.findTheDifference(s2, t2)
    # print(f"测试2: s='{s2}', t='{t2}' -> 被添加的字符: '{result2}'")
    
    # # 测试用例3
    # s3, t3 = "a", "aa"
    # result3 = solution.findTheDifference(s3, t3)
    # print(f"测试3: s='{s3}', t='{t3}' -> 被添加的字符: '{result3}'")
    
    # # 测试所有方法的一致性
    # test_cases = [
    #     ("abcd", "abcde"),
    #     ("", "y"),
    #     ("a", "aa"),
    #     ("abc", "abcc")
    # ]
    